package cn.com.forever.array;
/*
    给定一个数组arr，返回子数组的最大累加和
    例如，arr = [1, -2, 3, 5, -2, 6, -1]，所有子数组中，[3, 5, -2, 6]可以累加出最大的和12，所以返回12.
    题目保证没有全为负数的数据
    [要求]
    时间复杂度为O(n)，空间复杂度为O(1)
 */
public class 子数组的最大累加和问题 {
    public static void main(String[] args) {
        int[] arr = {1,-2,3};
        System.out.println(maxsumofSubarray(arr));
    }

    public static int maxsumofSubarray (int[] arr) {
        if(arr == null) return 0;
//        int n = arr.length;  动态规划写法
//        int[] dp = new int[n];
//        dp[0] = arr[0];
//        int max = arr[0];
//        for (int i = 1; i < n; i++) {
//            if(dp[i-1] <= 0){
//                dp[i] = arr[i];
//            }
//            else{
//                dp[i] = dp[i-1] + arr[i];
//            }
//            max = Math.max(max,dp[i]);
//        }
//        return max;

        int max = arr[0];
        int cur = arr[0];
        for (int i = 1; i < arr.length; i++) {
            cur += arr[i];
            max = Math.max(max,cur);
            cur = cur > 0? cur:0;
        }
        return max;
    }
}
